package labuladong;

import java.util.HashMap;

public class LRU {
    private HashMap<Integer,Node> map;
    private DoubleList cache;
    private int cap;
    public LRU(int capacity){
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
    int get(int key){
        if(!map.containsKey(key)){
            return -1;
        }
        int val = map.get(key).val;
        // 利用put方法把该数据提前
        put(key,val);
        return val;
    }

    private void put(int key, int val) {
        Node x = new Node(key,val);
        if(map.containsKey(key)){
            // 删除旧的节点，新的插到头部
            cache.remove(map.get(key));
            cache.addFirst(x);
            map.put(key, x);
        }else{
            if(cap == cache.size()){
                Node last = cache.removeLast();
                map.remove(last.key);
            }
            cache.addFirst(x);
            map.put(key, x);
        }
    }
}
class Node{
    public int key,val;
    public Node next,prev;
    public Node(int k, int v){
        this.key = k;
        this.val = v;
    }
}
/**
 * DouobleList
 */
class DoubleList {
    // 头部虚节点
    private Node head, tail;
    // 链表元素数
    private int size;
    public DoubleList(){
        head = new Node(0,0);
        tail = new Node(0,0);
        head.next=tail;
        tail.prev=head;
        size=0;
    }
    // 在链表头部添加节点
    public void addFirst(Node x){
        x.next = head.next;
        head.next.prev = x;
        x.prev = head;
        head.next = x;
        size++;
    }

    public void remove(Node x){
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size--;
    }

    public Node removeLast(){
        if(tail.prev == head) return null;
        Node last = tail.prev;
        remove(last);
        return last;
    }

    public int size(){
        return size;
    }
}
